package com.dataStructure.likedList;


/**
 * @author roger dai 
 * 
 * 双端队列：列表中的每个节点都包含了对前一个和后一个元素的引用. 应该有一个head以及last node的引用，但这里last node引用没加
 *
 * @param <E>
 */
public class MyLinkedList<E> {
	Node<E> head;
	
	public MyLinkedList(){
		head = new Node<E>(null, null, null);
	}
		
	/**
	 * 在队列尾端添加数据
	 * @param e
	 * @return
	 */
	public boolean add(E e){
		Node<E> h = head;
		for (; h.next!=null; h = h.next) {
			
		}
		Node<E>	newNode = new Node<E>(e, h, null);
		h.next = newNode;
		return false;
	}
	
	/** 
	 * 删除第一个找到的元素，找到并且删除了相应的点，返回true，否则 返回false
	 * @param e
	 * @return
	 */
	public boolean delete(E e){
		Node<E> h = head;
		for (; h.next!=null; h = h.next) {
			E content = h.getE();
			if (content == e || e.equals(content)) {
				if (h.equals(head)) { 		//first node
					head = head.next;
					head.previous = null;
				}else { 					//middle node
					h.previous.next = h.next;
					h.next.previous = h.previous;
				}
				
				return true;
			}
		}
		if (h.getE() == e || e.equals(h.getE()))  // last node
			h.previous.next = null;
		
		return false;
	}
	
	/**
	 * 获取队首元素
	 * @return
	 */
	public E getFirst(){
		return head.getE();
	}
	
	/**
	 * 获得队尾元素
	 * @return
	 */
	public E getLast(){
		Node<E> h = head;
		for (; h.next!=null; h = h.next) {
			
		}
		return h.getE();
	}
	
	public void clear(){
		for (Node<E> x = head; x != null; ) {
            Node<E> next = x.next;
            x.e = null;
            x.next = null;
            x.previous = null;
            x = next;
        }
	}
	
	/**
	 * 
	 * @return
	 */
//	public E element(){
//		return null;
//		
//	}
	
	public void disPlay() {
		if (head.next == null) { //空时不输出什么东西
			return ;
		}
		Node<E> h = head.next;
		for (; h.next!=null; h = h.next) {
			System.out.println(h.getE());
		}
		System.out.println(h.getE());
	}
	
	
	/** 节点类
	 * @author oracle
	 *
	 * @param <E>
	 */
	class Node<E>{
		Node<E> previous;
		Node<E> next;
		E e;  //content
		
		Node(E e,Node<E> p,Node<E> n){
			this.e = e;
			this.previous = p;
			this.next = n;
		}

		public Node<E> getPrevious() {
			return previous;
		}

		public void setPrevious(Node<E> previous) {
			this.previous = previous;
		}

		public Node<E> getNext() {
			return next;
		}

		public void setNext(Node<E> next) {
			this.next = next;
		}

		public E getE() {
			return e;
		}

		public void setE(E e) {
			this.e = e;
		}
		
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyLinkedList<String> stringLinkedList = new MyLinkedList<String>();
		stringLinkedList.add("1");
		stringLinkedList.add("2");
		stringLinkedList.add("3");
		stringLinkedList.disPlay();
		System.out.println("===========================");
		
		stringLinkedList.delete("2");
		stringLinkedList.delete("3");
		stringLinkedList.disPlay();
		System.out.println("===========================");
		
		stringLinkedList.add("2");
		stringLinkedList.add("5");
		stringLinkedList.disPlay();
		System.out.println("===========================");
		
		stringLinkedList.clear();
		stringLinkedList.disPlay();
		System.out.println("===========================");
		
		MyLinkedList<Integer> intLinkedList = new MyLinkedList<Integer>();
		intLinkedList.add(1);
		intLinkedList.add(4);
		intLinkedList.add(5);
		intLinkedList.add(2);
		intLinkedList.disPlay();
		
		intLinkedList.delete(4);
		intLinkedList.disPlay();
		
		
	}

}
